package hot100.logos31To40;

import hot100.datastruct.Node;

/**
 * @author logos
 * date 2025/7/13 11:37
 * @version v1.0
 * @Package hot100.logos31To40
 */
public class logos32 {

    /**
     * 32.随机链表的复制
     * https://leetcode.cn/problems/copy-list-with-random-pointer/description/?envType=study-plan-v2&envId=top-100-liked
     */
    class Solution {
        public Node copyRandomList(Node head) {
            if (head == null) {
                return null;
            }
            Node cur = head;
            Node next = null;
            Node node = null;
            while (cur != null) {
                node = new Node(cur.val);
                next = cur.next;
                node.next = next;
                cur.next = node;
                cur = next;
            }
            cur = head;
            node = cur.next;
            while (cur != null && node != null) {
                node.random = cur.random == null ? null : cur.random.next;
                cur = node.next;
                if (cur == null) {
                    break;
                }
                node = cur.next;
            }
            Node ans = head.next;
            cur = head;
            while (cur != null && cur.next != null) {
                next = cur.next.next;
                node = cur.next;
                cur.next = next;
                node.next = next != null ? next.next : null;
                cur = next;
            }
            return ans;
        }
    }
}
